package 递归回溯;

import com.alibaba.fastjson.JSON;

import java.util.*;

public class No90子集II {

    /**
     * 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
     * 说明：解集不能包含重复的子集。
     *
     * 示例:
     * 输入: [1,2,2]
     * 输出:
     * [
     *   [2],
     *   [1],
     *   [1,2,2],
     *   [2,2],
     *   [1,2],
     *   []
     * ]
     */

    private int[] arr;
    private List<List<Integer>> lists=new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        this.arr=nums;
        Deque<Integer> path=new ArrayDeque<>();
        dg(path,0);
        return lists;
    }

    private void dg(Deque<Integer> path,int start){

        if(path.size()==arr.length){
            lists.add(new ArrayList<>(path));
            return;
        }
        lists.add(new ArrayList<>(path));

        /**
         * 为start的->
         * 当前路径:[1]
         * 当前路径:[1,2]
         * 当前路径:[1,2,2]
         * 当前路径:[2]
         * 当前路径:[2,2]
         *
         * 为0的->
         * 当前路径:[1]
         * 当前路径:[1,2]
         * 当前路径:[2]
         */

        for (int i = start; i < arr.length; i++) {
            //
            /**
             * 重点:大于start和大于0有什么区别呢?
             * 大于start可以添加进当前元素
             * 大于0不可以添加进当前元素
             * 对于某些题一定要注意,我开始就是被这里踩坑了
             */
            if(i>start&&arr[i]==arr[i-1])
                continue;
            path.addLast(arr[i]);
            System.out.println("当前路径:"+JSON.toJSONString(path));
            dg(path,i+1);
            path.removeLast();
        }

    }

    public static void main(String[] args) {
        No90子集II n=new No90子集II();
        List<List<Integer>> lists = n.subsetsWithDup(new int[]{4,4,4,1,4});
        System.out.println(JSON.toJSONString(lists));
    }



}
